//移动零
/*给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1*/
void swap(int* a, int* b) {
    int tump = *a;
    *a = *b;
    *b = tump;
}
void moveZeroes(int* nums, int numsSize) {
    int cur = 0;
    int dest = -1;
    while (cur < numsSize) {
        if (nums[cur]) {
            dest++;
            swap(nums + cur, nums + dest);//交换数字，将0放到非0区间里。
        }
        cur++;
    }
    return;
}
//本题可看作是数组划分，把数组划分为不同的区间，第一个区间是非0区间[0,dest],第二个区间是0区间[dest+1,cur-1],第三个区间是[cur,n]。
//当cur超数组的边界，就只剩下两个区间，第一个区间是非0，第二个区间是0。（此方法跟快排排序有关联）


//复写零
/*给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
1 <= arr.length <= 104
0 <= arr[i] <= 9

 */
 void duplicateZeros(int* arr, int arrSize) {
    int cur = -1;
    int dest = -1;
    //第一步先找到覆盖后的数组的最后一位数字，也就是下标是cur的数字。
    while (dest < arrSize - 1) {
        if (arr[++cur]) {
            dest++;
        } else {
            dest++;
            dest++;
        }
    }
    //第二步注意边界问题，dest可能会存在越界的情况，出现越界一定是下标cur的数字是0，所以，数组尾部是0。
    if (dest >= arrSize) {
        arr[arrSize - 1] = 0;
        cur--;
        dest--;
        dest--;
    }
    //第三步从数组尾部向头部，进行覆盖。
    while (dest >= 0) {
        if (arr[cur]) {
            arr[dest--] = arr[cur--];
        } else {
            cur--;
            arr[dest--] = 0;
            arr[dest--] = 0;
        }
    }
    return;
}
//本题可以先分开成两数组进行覆盖，然后思考怎么优化成原地覆盖。然后发现从后面可以覆盖，然后分成三步，第一步第一步先找到覆盖后的数组的最后一位数字。第二步注意边界问题。第三步从数组尾部向头部，进行覆盖。



//快乐数
/*编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
提示：

1 <= n <= 2^31 - 1*/

int make_nums(int n)
{
    int sum=0;
    while(n)
    {
        sum+=(n%10)*(n%10);
        n/=10;
    }
    return sum;
}
bool isHappy(int n) {
    int slow=n;
    int quick=n;
    while(1)
    {
        slow=make_nums(slow);
        quick=make_nums(make_nums(quick));
        if(slow==quick)
        {
            if(slow==1)
            return true;
            return false;
        }
    }
    return false;
}
//本题是分三种情况，第一种情况是无限循环数是非1，第二种是无限循环数是1，第三种是无限不循环数。我们首先排除第三种，是因为根据鸽巢原理，第三种情况不可能存在。
//剩下两种情况，两者都是循环，可以通过双指针思想，来判断是否成环，因为第二种情况双指针相遇一定是1，而另一种是非1，即可将两种情况区分。